package binary;

import java.util.Stack;

class BinaryTree {
    //以内部类的方式定义树节点
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public int i;
    //递归创建树
    public TreeNode createTree(String str) {
        if(str==null || str.charAt(i)=='#') {
            i++;
            return null;
        }
            TreeNode root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);

        return root;
    }

    //前序遍历
    public void preorderTraversal(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
    }

    //oj解题：https://leetcode.cn/problems/construct-string-from-binary-tree/
    public String tree2str(TreeNode root) {
        //前序遍历
        //涉及到字符串拼接 需要使用StringBuilder
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder stringBuilder) {
        //root!=null
        //先拼接根
        stringBuilder.append(root.val);

        if(root.left!=null) {
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        } else {
            if(root.right!=null) {
                stringBuilder.append("()");
            } else{
                return;
            }
        }

        if(root.right!=null) {
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }
    }

    //非递归中序遍历
    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null || !stack.empty()) {

            while(cur!=null) {
                //遍历树
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            System.out.print(cur.val+" ");
            cur = cur.right;
        }
    }

    //非递归后序遍历
    /**
     * 非递归后续遍历需要考虑死循环的问题
     * 故需要定义一个记录器，队出栈的节点进行记录*/
    public void postorder(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null || !stack.empty()) {
            //先将cur走到树最左边节点
            while(cur!=null) {
                stack.push(cur);
                cur = cur.left;
            }
            /*因为后序遍历为 左 右 根，故此时需要判定cur.right是否有根
             * 若是无根则直接打印并出栈
             * 若是有根，则需要重复上文循环，走到该树最左边节点*/
            TreeNode top = stack.peek();
            if(top.right==null || top.right == prev) {
                System.out.print(top.val+" ");
                prev = stack.pop();
            } else{
                cur = top.right;
            }
        }
    }
}